/**
 * 编写一个函数来查找字符串数组中的最长公共前缀。
 *
 * @author suncp
 * @date 2020/12/25 18:13
 */
public class LongestCommonPrefix {
    public static void main(String[] args) {
//        String[] strs = new String[]{"flower", "flow", "flight"};
//        String[] strs = new String[]{"flower","flower","flower","flower"};
//        String[] strs = new String[]{"dog", "racecar", "car"};
//        String[] strs = new String[]{"D"};
//        String[] strs = new String[]{"", ""};
        String[] strs = new String[]{"ab", "a"};
//        String[] strs = new String[]{};
        String s = longestCommonPrefix(strs);
        System.out.println(s);
    }

    /**
     * 4ms|37.9MB
     *
     * @param strs
     * @return
     */
    private static String longestCommonPrefix(String[] strs) {
        String compareStr = "";
        int index1 = 1;
        if (strs != null && strs.length != 0) {
            // 第一个字符串处理
            for (int x = 1; x < strs[0].length() + 1; x++) {
                // 截取第一个字符串的前1位,递增获取
                compareStr = strs[0].substring(0, x);
                // 下标
                index1 = x;

                // 外层循环,定位索引
                for (int i = 1; i < strs.length; i++) {
                    if (x <= strs[i].length()) {
                        if (!compareStr.equals(strs[i].substring(0, x))) {
                            if (x == 1) {
                                return "";
                            } else {
                                return compareStr.substring(0, compareStr.length() - 1);
                            }
                        }
                    } else {
                        return compareStr.substring(0, compareStr.length() - 1);
                    }
                }
            }
        } else {
            return "";
        }
        // 判断两种情况: 1.多个不一样的字符串,返回""; 2.一个字符串,返回该字符串
        if (index1 == 1 && strs.length == 1) {
            return strs[0];
        }
        return compareStr;
    }

    /**
     * 0ms|36.5MB
     *
     * @param strs
     * @return
     */
    private String test(String[] strs) {
        String a = "";
        try {
            a = strs[0];
            for (String str : strs) {
                // 若a已经减为""，则说明无公共前缀，直接返回
                if (a == "") return a;
                // 若a在当前str中匹配不上，则减少字符串a的长度，再次尝试匹配
                while (!str.startsWith(a)) {
                    a = a.substring(0, a.length() - 1);
                }
            }
            return a;
        } catch (Exception e) {
            return a;
        }
    }
}
